package listbyorder.access101_200.test124;

import listbyorder.utils.TreeNode;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/8 13:46
 */
public class Solution1 {

    // 定义一个全局变量res
    int res = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dp(root);
        return res;
    }

    // 小黑核，计算当前根节点到叶子节点的最长路径和
    private int dp(TreeNode root) {
        if (root == null) return 0;

        int left = Math.max(dp(root.left), 0);   // 计算出左子树的最大值（此结果是从上到下最大路径的长度，不是我们要求解的）
        int right = Math.max(dp(root.right), 0);
        res = Math.max(res, left + right + root.val);

        return root.val + Math.max(left, right);
    }
}
